/**
 * @author zerorain
 **/
public class eee {
    public static void main(String[] args) {

    }
    public static void quickSort2(int [] arr){
        quickSortInternal2(arr,0,arr.length - 1);
    }

    private static void quickSortInternal2(int[] arr, int l, int r) {
        if( r - l <= 15){
            insertionSort(arr,l,r);
            return;
        }
        int p = partition2(arr,l,r);
        quickSortInternal2(arr,l,p - 1);
        quickSortInternal2(arr,p + 1,r);
    }

    private static int partition2(int[] arr, int l, int r) {
        int v = arr[l];
        int i = l + 1;
        int j = r;
        while (true){
            while(i <= j && arr[i] < v){
                i++;
            }
            while(i <= j && arr[j] > v){
                j--;
            }
            if(i > j){
                break;
            }
            swap(arr,i,j);
            i++;
            j--;
        }
        swap(arr,l,j);
        return j;
    }

    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }
    public static void MergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length);
    }

    private static void mergeSortInternal(int[] arr, int l, int r) {
        if(r - l <= 15){
            insertionSort(arr,l,r);
            return;
        }
        int mid = (l + r) / 2;
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid + 1,r);
        if (arr[mid] > arr[mid + 1]) {
            merge(arr,l,mid,r);
        }
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        // 先创建一个新的临时数组aux
        int[] aux = new int[r - l + 1];
        // 将arr元素值拷贝到aux上
        for (int i = 0; i < aux.length; i++) {
            aux[i] = arr[i + l];
        }
        // i就是左侧小数组的开始索引
        int i = l;
        // j就是右侧小数组的开始索引
        int j = mid + 1;
        // k表示当前正在合并的原数组的索引下标
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左侧区间已经被处理完毕，只需要将右侧区间的值拷贝原数组即可
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 右侧区间已经被处理完毕，只需要将左侧区间的值拷贝到原数组即可
                arr[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 此时左侧区间的元素值较小，相等元素放在左区间，保证稳定性
                arr[k] = aux[i - l];
                i ++;
            }else {
                // 右侧区间的元素值较小
                arr[k] = aux[j - l];
                j ++;
            }
        }
    }

    public static void HeapSort(int[] arr){
        createHeap(arr);
        for (int i = 0; i < arr.length - 1; i++) {
            swap(arr,0,arr.length - 1 - i);
            shiftDown(arr,arr.length - 1 - i,0);
        }
    }
    public static void createHeap(int [] arr){
        for (int i = (arr.length - 1) / 2;i >= 0; i--) {
            shiftDown(arr,arr.length,i);
        }
    }

    private static void shiftDown(int[] arr, int size, int index) {
        int left = 2 * index + 1;
        while (left < size){
            int max = left;
            int right = 2 * index + 2;
            if(right < size){
                if(arr[right] > arr[left]){
                    max = right;
                }
            }
            if(arr[index] >= arr[max]){
                break;
            }
            int t = arr[index];
            arr[index] = arr[max];
            arr[max] = t;
            index = max;
            left = 2 * index + 1;
        }
    }

    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = arr[i];
    }
    public static void ShellSort(int[] arr){
        int gap = arr.length;
        while (gap > 1){
            intsetShellSort(arr,gap);
            gap = (gap / 3) + 1;
        }
        intsetShellSort(arr,1);
    }
    public static void intsetShellSort(int[] arr,int gap){
        for (int i = 1; i < arr.length ; i++) {
            int val = arr[i];
            int j = i - gap;
            for (;j>= 0 && arr[j] > val; j-=gap){
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = val;
        }
    }
    public static void insertSort(int[] arr){
        for (int i= 1 ; i < arr.length;i++ ){
            int val = arr[i];
            int j = i - 1;
            for (; j >= 0 && arr[j] > val ; j++) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = val;
        }
    }
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwaped = false;
            for (int j = 0; j < arr.length - 1 -i; j++) {
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    isSwaped = true;
                }
            }
            if(!isSwaped){
                break;
            }
        }
    }
    public static void selectSortOP(int[] arr){
        int low = 0;
        int high = arr.length - 1;
        while (low <= high){
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if(arr[i] < arr[min]){
                    min = i;
                }
                if(arr[i] > arr[max]){
                    max = i;
                }
            }
            int temp = 0;
            temp = arr[min];
            arr[min] = arr[low];
            arr[low] = temp;
            if(max == low){
                max = min;
            }
            temp = arr[max];
            arr[max] = arr[high];
            arr[high] = temp;
            low++;
            high--;
        }
    }
    public static void  selectSort(int[] arr){
        for(int i = 0 ; i < arr.length - 1; i++){
            int min = i;
            for (int j = i + 1; j < arr.length; j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            int temp = 0;
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
    public static void insert(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >= 1 && arr[j] < arr[j - 1] ; j--) {
                int temp = 0;
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }
    public static void insertSortBS(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];
            int left = 0;
            int right = i;
            while(left < right){
                int mid = (left +right)/2;
                if(val < arr[mid]){
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i ; j < left; j--){
                arr[j] = arr[j - 1];
            }
            arr[left] = val;
        }
    }
}

